{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Line of Consecutive One in Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestLine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中最长的连续1线段"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code>m x n</code>&nbsp;的二进制矩阵 <code>mat</code><b>&nbsp;</b>，返回矩阵中最长的连续1线段。</p>\n",
    "\n",
    "<p>这条线段可以是水平的、垂直的、对角线的或者反对角线的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/24/long1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]\n",
    "<strong>输出:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/24/long2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>mat[i][j]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-line-of-consecutive-one-in-matrix](https://leetcode.cn/problems/longest-line-of-consecutive-one-in-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-line-of-consecutive-one-in-matrix](https://leetcode.cn/problems/longest-line-of-consecutive-one-in-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,0],[0,1,1,0],[0,0,0,1]]', '[[1,1,1,1],[0,1,1,0],[0,0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def overflow(self, i, j):\n",
    "        return i < 0 or j < 0 or i >= len(self.m) or j >= len(self.m[0])\n",
    "    \n",
    "    def count(self, i, j, direction_i, direction_j):\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        while not self.overflow(i, j):\n",
    "            if self.m[i][j]:\n",
    "                cur += 1\n",
    "                ans = max(ans, cur)\n",
    "            else:\n",
    "                cur = 0\n",
    "            i += direction_i\n",
    "            j += direction_j\n",
    "        return ans\n",
    "\n",
    "    def longestLine(self, M: List[List[int]]) -> int:\n",
    "        if not M:\n",
    "            return 0\n",
    "        self.m = M\n",
    "        ans = 0\n",
    "        for i in range(len(M)):\n",
    "            # 左边界为起点，向右\n",
    "            ans = max(ans, self.count(i, 0, 0, 1))\n",
    "            # 左边界为起点，向右下\n",
    "            ans = max(ans, self.count(i, 0, 1, 1))\n",
    "            # 右边界为起点，向左下\n",
    "            ans = max(ans, self.count(i, len(M[0]) - 1, 1, -1))\n",
    "        for j in range(len(M[0])):\n",
    "            # 上边界为起点，向下\n",
    "            ans = max(ans, self.count(0, j, 1, 0))\n",
    "            # 上边界为起点，向右下\n",
    "            ans = max(ans, self.count(0, j, 1, 1))\n",
    "            # 上边界为起点，向左下\n",
    "            ans = max(ans, self.count(0, j, 1, -1))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        # 列只往下走，行只往右走，对角线只往右下走\n",
    "        res = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # if m == n == 1: return 1 if mat[0][0] == 1 else 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "\n",
    "                    if j < n: # 行\n",
    "                        if j == 0 or mat[i][j-1] != 1:\n",
    "                            tmp_j = j\n",
    "                            while tmp_j < n and mat[i][tmp_j] == 1:\n",
    "                                tmp_j += 1\n",
    "                            res = max(res, tmp_j-j)\n",
    "\n",
    "                    if i < m: # 列\n",
    "                        if i == 0 or mat[i-1][j] != 1:\n",
    "                            tmp_i = i\n",
    "                            while tmp_i < m and mat[tmp_i][j] == 1:\n",
    "                                tmp_i += 1\n",
    "                            res = max(res, tmp_i-i)\n",
    "\n",
    "                    if i < m and j < n: # 对角线\n",
    "                        if i == 0 or j == 0 or mat[i-1][j-1] != 1:\n",
    "                            tmp_i, tmp_j = i ,j\n",
    "                            while tmp_i<m and tmp_j<n and mat[tmp_i][tmp_j] == 1:\n",
    "                                tmp_i += 1\n",
    "                                tmp_j += 1\n",
    "                            res = max(res, tmp_i-i)\n",
    "                    \n",
    "                    if i < m and j >= 0: # 反对角线\n",
    "                        if i == 0 or j == n-1 or mat[i-1][j+1] != 1:\n",
    "                            tmp_i, tmp_j = i ,j\n",
    "                            while tmp_i<m and tmp_j>=0 and mat[tmp_i][tmp_j] == 1:\n",
    "                                tmp_i += 1\n",
    "                                tmp_j -= 1\n",
    "                            res = max(res, tmp_i-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        ret=0\n",
    "        for i in range(len(mat)):\n",
    "            count=0\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]==1:\n",
    "                    count+=1\n",
    "                else:\n",
    "                    ret=max(ret,count)\n",
    "                    count=0\n",
    "            ret=max(ret,count)\n",
    "        for j in range(len(mat[0])):\n",
    "            count=0\n",
    "            for i in range(len(mat)):\n",
    "                if mat[i][j]==1:\n",
    "                    count+=1\n",
    "                else:\n",
    "                    ret=max(ret,count)\n",
    "                    count=0\n",
    "            ret=max(ret,count)\n",
    "        def f():\n",
    "            nonlocal ret\n",
    "            for j in range(len(mat[0])):\n",
    "                add=0\n",
    "                count=0\n",
    "                for _ in range(len(mat)):\n",
    "                    if j+add<len(mat[0]) and add<len(mat):\n",
    "                        if mat[add][j+add]==1:\n",
    "                            count+=1\n",
    "                        else:\n",
    "                            ret=max(ret,count)\n",
    "                            count=0\n",
    "                    else:\n",
    "                        ret=max(ret,count)\n",
    "                        break\n",
    "                    add+=1\n",
    "                ret=max(ret,count)\n",
    "            for i in range(1,len(mat)):\n",
    "                add=0\n",
    "                count=0\n",
    "                for _ in range(len(mat)):\n",
    "                    if add<len(mat[0]) and i+add<len(mat):\n",
    "                        if mat[i+add][add]==1:\n",
    "                            count+=1\n",
    "                        else:\n",
    "                            ret=max(ret,count)\n",
    "                            count=0\n",
    "                    else:\n",
    "                        ret=max(ret,count)\n",
    "                        break\n",
    "                    add+=1\n",
    "                ret=max(ret,count)\n",
    "        f()\n",
    "        for i in range(len(mat)):\n",
    "            mat[i].reverse()\n",
    "        f()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        ans = 0\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    if j == 0 or row[j - 1] == 0:\n",
    "                        h,k = 0,j\n",
    "                        while k < n and row[k] == 1:\n",
    "                            h += 1\n",
    "                            k += 1\n",
    "                        ans = max(ans,h)\n",
    "                    if i == 0 or mat[i - 1][j] == 0:\n",
    "                        v,k = 0,i\n",
    "                        while k < m and mat[k][j] == 1:\n",
    "                            v += 1\n",
    "                            k += 1\n",
    "                        ans = max(ans,v)\n",
    "                    if i == 0 or j == 0 or mat[i - 1][j - 1] == 0:\n",
    "                        l1,ni,nj = 0,i,j\n",
    "                        while ni < m and nj < n and mat[ni][nj] == 1:\n",
    "                            l1 += 1\n",
    "                            ni += 1\n",
    "                            nj += 1\n",
    "                        ans = max(ans,l1)\n",
    "                    if i == 0 or j == n - 1 or mat[i - 1][j + 1] == 0:\n",
    "                        l2,ni,nj = 0,i,j\n",
    "                        while ni < m and nj >= 0 and mat[ni][nj] == 1:\n",
    "                            l2 += 1\n",
    "                            ni += 1\n",
    "                            nj -= 1\n",
    "                        ans = max(ans,l2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 扫描行\n",
    "        for k in range(m):\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                if mat[k][i] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                j = i + 1\n",
    "                while j < n and mat[k][j] == 1:\n",
    "                    j += 1\n",
    "                ans = max(ans, j - i)\n",
    "                i = j\n",
    "        \n",
    "        # 扫描列\n",
    "        for k in range(n):\n",
    "            i = 0\n",
    "            while i < m:\n",
    "                if mat[i][k] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                j = i + 1\n",
    "                while j < m and mat[j][k] == 1:\n",
    "                    j += 1\n",
    "                ans = max(ans, j - i)\n",
    "                i = j\n",
    "          \n",
    "        # 扫描对角线\n",
    "        for k in range(-m+1, n):\n",
    "            if k <= 0:\n",
    "                xi, yi = -k, 0\n",
    "            else:\n",
    "                xi, yi = 0, k\n",
    "            while xi < m and yi < n:\n",
    "                if mat[xi][yi] == 0:\n",
    "                    xi += 1\n",
    "                    yi += 1\n",
    "                    continue\n",
    "                xj, yj = xi+1, yi+1\n",
    "                while xj < m and yj < n and mat[xj][yj] == 1:\n",
    "                    xj += 1\n",
    "                    yj += 1\n",
    "                ans = max(ans, xj - xi)\n",
    "                xi, yi = xj, yj\n",
    "        \n",
    "        # 扫描反对角线\n",
    "        for k in range(-m+1, n):\n",
    "            if k <= 0:\n",
    "                xi, yi = -k , n-1\n",
    "            else:\n",
    "                xi, yi = 0, k\n",
    "            while xi < m and yi >= 0:\n",
    "                if mat[xi][yi] == 0:\n",
    "                    xi += 1\n",
    "                    yi -= 1\n",
    "                    continue\n",
    "                xj, yj = xi+1, yi-1\n",
    "                while xj < m and yj >= 0 and mat[xj][yj] == 1:\n",
    "                    xj += 1\n",
    "                    yj -= 1\n",
    "                ans = max(ans, xj - xi)\n",
    "                xi, yi = xj, yj\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        #四个方向各考虑一遍DP即可(也算是线性DP,只是要考虑不同方向)\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=0\n",
    "        #横着的\n",
    "        for i in range(m):\n",
    "            pre=0\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #竖着的\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(m):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        for i in range(m):\n",
    "            x,y=i,0\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        #反斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            x,y=i,n-1\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        #四个方向各考虑一遍DP\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=0\n",
    "        #横着的\n",
    "        for i in range(m):\n",
    "            pre=0\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #竖着的\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(m):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        for i in range(m):\n",
    "            x,y=i,0\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        #反斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            x,y=i,n-1\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        #四个方向各考虑一遍DP\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=0\n",
    "        #横着的\n",
    "        for i in range(m):\n",
    "            pre=0\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #竖着的\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(m):\n",
    "                if mat[i][j]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "        #斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        for i in range(m):\n",
    "            x,y=i,0\n",
    "            pre=0\n",
    "            while x<m and y<n:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y+=1\n",
    "        #反斜着的\n",
    "        for i in range(n):\n",
    "            x,y=0,i\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            x,y=i,n-1\n",
    "            pre=0\n",
    "            while x<m and y>=0:\n",
    "                if mat[x][y]==1:\n",
    "                    pre+=1\n",
    "                else:\n",
    "                    pre=0\n",
    "                ans=max(ans,pre)\n",
    "                x+=1\n",
    "                y-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        f = [[0] * 4 for i in range(n + 1)]\n",
    "        ans = 0\n",
    "        for i in range(0, m):\n",
    "            g = [[0] * 4 for i in range(n + 1)]\n",
    "            for j in range(n-1, -1, -1):\n",
    "                g[j][0] = mat[i][j] + g[j + 1][0] if mat[i][j] == 1 else 0\n",
    "                g[j][1] = mat[i][j] + f[j + 1][1] if mat[i][j] == 1 else 0\n",
    "                g[j][2] = mat[i][j] + f[j][2] if mat[i][j] == 1 else 0\n",
    "                g[j][3] = (mat[i][j] + (0 if j == 0 else f[j - 1][3])) if mat[i][j] == 1 else 0\n",
    "            f = g\n",
    "            ans = max(ans, max(max(t) for t in f))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "      m = len(mat)\n",
    "      n = len(mat[0])\n",
    "      mi = min(m, n)\n",
    "\n",
    "      res = 0\n",
    "\n",
    "      # vertical\n",
    "      for i in range(m):\n",
    "        tmp = 0\n",
    "        for j in range(n):\n",
    "          if mat[i][j] == 0:\n",
    "            res = max(res, tmp)\n",
    "            tmp = 0\n",
    "          else:\n",
    "            tmp += 1\n",
    "        res = max(res, tmp)\n",
    "\n",
    "      # horizontal\n",
    "      for j in range(n):\n",
    "        tmp = 0\n",
    "        for i in range(m):\n",
    "          if mat[i][j] == 0:\n",
    "            res = max(res, tmp)\n",
    "            tmp = 0\n",
    "          else:\n",
    "            tmp += 1\n",
    "        res = max(res, tmp)\n",
    "\n",
    "      # diag\n",
    "      diag = [[0] * n for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          if mat[i][j] == 0:\n",
    "            diag[i][j] = 0\n",
    "          else:\n",
    "            diag[i][j] = 1 + (0 if i == 0 or j == 0 else diag[i - 1][j - 1])\n",
    "      tmp = max(map(max, diag))\n",
    "      res = max(res, tmp)\n",
    "\n",
    "      # antidiag\n",
    "      antidiag = [[0] * n for _ in range(m)]\n",
    "      for i in range(m):\n",
    "        for j in range(n - 1, -1, -1):\n",
    "          if mat[i][j] == 0:\n",
    "            antidiag[i][j] = 0\n",
    "          else:\n",
    "            antidiag[i][j] = 1 + (0 if i == 0 or j == n - 1 else antidiag[i - 1][j + 1])\n",
    "\n",
    "      tmp = max(map(max, antidiag))\n",
    "      res = max(res, tmp)\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        def check(lst):\n",
    "            res = cnt = 0 if not lst else 1\n",
    "            n = len(lst)\n",
    "            for i in range(n - 1):\n",
    "                if lst[i] + 1 == lst[i + 1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    res = max(res, cnt)\n",
    "                    cnt = 1\n",
    "            res = max(res, cnt)\n",
    "            return res\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            row = [j for j in range(n) if mat[i][j]]\n",
    "            cnt = check(row)\n",
    "            res = max(res, cnt)\n",
    "        for j in range(n):\n",
    "            col = [i for i in range(m) if mat[i][j]]\n",
    "            cnt = check(col)\n",
    "            res = max(res, cnt)\n",
    "        left = defaultdict(list)\n",
    "        right = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    left[i + j].append(i)\n",
    "                    right[i - j].append(i)\n",
    "        for lst in left.values():\n",
    "            cnt = check(lst)\n",
    "            res = max(res, cnt)\n",
    "        for lst in right.values():\n",
    "            cnt = check(lst)\n",
    "            res = max(res, cnt)\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        ans = 1 if mat[0][0] else 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i][j - 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(1, n):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j - 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j + 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        ans = 1 if mat[0][0] else 0        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i][j - 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(1, n):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j - 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        tmp = copy.deepcopy(mat)\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            for i in range(1, m):\n",
    "                if tmp[i][j]:\n",
    "                    tmp[i][j] += tmp[i - 1][j + 1]\n",
    "                    ans = max(ans, tmp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[ [0] * 4 for _ in range(n + 2)] for _ in range(m + 2)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if mat[i - 1][j - 1] == 1:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j - 1][1] + 1\n",
    "                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1\n",
    "                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1\n",
    "                    result = max(result, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[ [0] * 4 for _ in range(n + 2)] for _ in range(m + 2)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if mat[i - 1][j - 1] == 1:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j - 1][1] + 1\n",
    "                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1\n",
    "                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1\n",
    "                    result = max(result, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[ [0] * 4 for _ in range(n + 2)] for _ in range(m + 2)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if mat[i - 1][j - 1] == 1:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j - 1][1] + 1\n",
    "                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1\n",
    "                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1\n",
    "                    result = max(result, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        ans = 0\n",
    "        f = [[[0]*4 for _ in range(n + 2)] for _ in range(m + 1)]\n",
    "        for i in range(1,m + 1):\n",
    "            for j in range(1,n + 1):\n",
    "                if mat[i - 1][j - 1] == 1:\n",
    "                    f[i][j][0] = f[i][j - 1][0] + 1\n",
    "                    f[i][j][1] = f[i - 1][j][1] + 1\n",
    "                    f[i][j][2] = f[i - 1][j - 1][2] + 1\n",
    "                    f[i][j][3] = f[i - 1][j + 1][3] + 1\n",
    "                    ans = max(ans,max(f[i][j]))\n",
    "        return ans                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestLine(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[ [0] * 4 for _ in range(n + 2)] for _ in range(m + 2)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if mat[i - 1][j - 1] == 1:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j - 1][1] + 1\n",
    "                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1\n",
    "                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1\n",
    "                    result = max(result, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])\n",
    "        return result\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
